# -*- coding: utf-8 -*-

# # 问题描述
# 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)
# 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水

# 说明：你不能倾斜容器，且 n 的值至少为 2。

# 示例:
# 输入: [1,8,6,2,5,4,8,3,7]
# 输出: 49

# # 笨方法，结果时间超出了限制
# class Solution(object):
#     def maxArea(self, height):
#         """
#         :type height: List[int]
#         :rtype: int
#         """
#         max_area = 0;
#         for i in xrange(0,len(height)):
#             for j in xrange(1,len(height)):
#                 v = min(height[i], height[j]);
#                 if v * abs(j - i) < max_area:
#                     continue;
#                 max_area = v * abs(j - i);
#                 print [i, j, max_area];
#         return max_area;

# # 反思：
# # 一下2种解决方案在一定程度上降低了时间复杂度，可是本质上却并没有改变
# # 算法考虑的是时间复杂度的上限，因为上限总是会出现

# # 使用组合而不使用排列，把时间复杂度下降到上面的1/2
# # 时间仍然超出了限制
# class Solution(object):
#     def maxArea(self, height):
#         """
#         :type height: List[int]
#         :rtype: int
#         """
#         max_area = 0;
#         for i in xrange(0,len(height)):
#             for j in xrange(i + 1,len(height)):
#                 v = min(height[i], height[j]);
#                 if v * abs(j - i) < max_area:
#                     continue;
#                 max_area = v * abs(j - i);
#                 # print [i, j, max_area];
#         return max_area;

# # 首先计算i位置的最大可能容量，当已知最大值大于它时，直接跳过
# # 时间仍然超出限制
# class Solution(object):
#     def maxArea(self, height):
#         """
#         :type height: List[int]
#         :rtype: int
#         """
#         max_area = 0;
#         for i in xrange(0, len(height) - 1):
#             max_i_area = height[i] * (len(height) - 1 - i);
#             if(max_area > max_i_area):
#                 continue;
#             for j in xrange(len(height) - 1, i, -1):
#                 v = min(height[i], height[j]);
#                 if max_area < v * (j - i):
#                     max_area = v * (j - i);
#                 if height[j]>=height[i]:
#                     break;
#         return max_area;

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max_area = 0;
        index_begin = 0;
        index_end = len(height);
        while index_begin < index_end:
            v = min(height[index_begin], height[index_end - 1]);
            interval = index_end - 1 - index_begin;
            if max_area < v * interval:
                max_area = v * interval;
            if height[index_begin] < height[index_end - 1]:
                index_begin += 1;
            else:
                index_end -= 1;
        return max_area;

t = Solution();
print t.maxArea([10,14,10,4,10,2,6,1,6,12]);